Chapter 13

Useful Algorithms

The concept of algorithm is of central importance, especially for arithmetic, and

even more particularly for operations carried out by mathematical machines such as

digital computers. An algorithm is defined as a process of solving problems based

on repeatedly carrying out a strictly defined procedure. A classical example is the

Euclidean algorithm for finding the greatest common divisor of two natural numbers

aa and bb.

Example. Supposea greater than ba > b; divideaa bybb to yield either the quotientq 1q1 or the remain-

der r 2r2 (if bb does not divide aa), that is,

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayouta = bq1 + r2 ,

0 < r2 < b .

(13.1)

Then if r 2 not equals 0r2 /= 0, divide bb by r 2r2:

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutb = r2q2 + r3 ,

0 < r3 < r2 ,

(13.2)

and continue by dividing r 2r2 by r 3r3 until the remainder ineluctably becomes zero.

Writing

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutrn−2 = rn−1qn−1 + rn ,

(13.3)

rn−1 = rnqn ,

(13.4)

then it is clear that r Subscript nrn is the greatest common divisor of aa and bb.

By way of explanation, note that if two integers ll and mm have a common divisor

dd, then for any integers hh and kk, the number h l plus k mhl + km will also be divisible by dd.

Denoting the greatest common divisor ofaa andbb bydeltaδ, from Eq. (13.1) it is clear that

deltaδ is a divisor of r 2r2, from Eq. (13.2) it is also a divisor of r 3r3, and from Eq. (13.3) it is

also a divisor of r Subscript nrn, which is itself a common divisor of aa and bb, since from these

equations it also follows that r Subscript nrn divides r Subscript n minus 1rn−1, r Subscript n minus 2rn−2, and so forth. Thus, deltaδ is identical

© Springer Nature Switzerland AG 2023

J. Ramsden, Bioinformatics, Computational Biology,

https://doi.org/10.1007/978-3-030-45607-8_13

157